#include <stdio.h>
#include <stdlib.h>

#define N 100
#define INF 65535

int num;                 //顶点数
int graph[N][N];
int dist[N];
int path[N];
int visited[N];
int num;

void input() {
    int i, j;
    scanf("%d", &num);
    for (i = 0; i < num; i++) {
        for (j = 0; j < num; j++) {
            scanf("%d", &graph[i][j]);
            if (graph[i][j] == 0) {
                graph[i][j] = INF;
            }
        }
    }
}


void test_input() {
    int i, j;
    num = 9;
    for (i = 0; i < num; i++)/* 初始化图 */
       {
           for ( j = 0; j < num; j++)
           {
               if (i==j) {
                   graph[i][j]=0;
               }
               else {
                   graph[i][j] = INF;
                   graph[j][i] = INF;
               }
           }
       }
       graph[0][1]=1;
       graph[0][2]=5;
       graph[1][2]=3;
       graph[1][3]=7;
       graph[1][4]=5;
       graph[2][4]=1;
       graph[2][5]=7;
       graph[3][4]=2;
       graph[3][6]=3;
       graph[4][5]=3;
       graph[4][6]=6;
       graph[4][7]=9;
       graph[5][7]=5;
       graph[6][7]=2;
       graph[6][8]=7;
       graph[7][8]=4;
       for(i = 0; i < num; i++)
       {
           for(j = i; j < num; j++)
           {
               graph[j][i] = graph[i][j];
           }
       }
}

void dijkstra(int v0)   //v0表示源顶点
{
    int i, j, k, t;
    int min, u;
    //init
    for(i = 0; i < num; i++)  {
        if(graph[v0][i]>0 && i != v0) {
            dist[i] = graph[v0][i];
            path[i] = v0;
        }
        else {
            dist[i] = INF;
            path[i] = -1;
        }
        visited[i] = 0;
        path[v0] = v0;
        dist[v0] = 0;
    }
    visited[v0] = 1;
    for(i = 1; i < num; i++)     //循环扩展n-1次
    {
        min = INF;
        for(j = 0; j < num; j++)    //寻找未被扩展的权值最小的顶点
        {
            if( !visited[j] && dist[j] < min)
            {
                min = dist[j];
                u = j;
            }
        }
        visited[u] = 1;
        for(k = 0; k < num; k++)   {
             //更新dist数组的值和路径的值
            t = min + graph[u][k];
            if( !visited[k] && graph[u][k] > 0 && t < dist[k])  {
                dist[k] = t;
                path[k] = u;
            }
        }
    }
}

void print_path(int beg, int end)   //打印最短路径上的各个顶点
{
    int s[N], top = 0;
    int v = end, u = v;
    printf("%d -> %d: ", beg, v);
    while(v != beg) {
        s[top++] = v; //s.push(v);
        v = path[v];
    }
    s[top++] = v;//s.push(v);
    while(top > 1) {
        printf("%d-", s[--top]);
    }
    printf("%d", end);
}

void output(int v0) {
    int i;
    for(i = 0; i < num; i++) {
        if(i!=v0) {
            print_path(v0, i);
            printf(" distance: %d\n", dist[i]);
        }
    }
}

int main(int argc, char *argv[])
{
    int v0;
    test_input();
    //scanf("%d", &v0);
    v0 = 0;
    dijkstra(v0);
    output(v0);
    return 0;
}
